Various directory systems have been used in the prior art to organize electronically-stored information in a communications network and to facilitate subsequent retrieval by a user. Hierarchically structured directories, such as X.500, have recently proliferated with the growth of the Internet, and are being used to store not only address books and contact information for people but also a range of other types of information—such as personal profiles, network resource information, and network and service policies. These directory systems provide a means for managing scale and heterogeneity, while allowing for conceptual unity and autonomy across multiple directory servers in the network, in a way far superior to what conventional relational or object-oriented databases offer. For example, network directory services based on the Lightweight Directory Access Protocol (LDAP) have proven quite popular recently. See “Lightweight Directory Access Protocol,” RFC 1777, Network Working Group, IETF 1994; “Lightweight Directory Access Protocol (v3),” RFC 2251, Network Working Group, IETF 1997. LDAP is a “lighter” version of X.500's Directory Access Protocol and, like X.500, organizes directory entries into a hierarchical namespace that can be accessed by a distinguished name or by using declarative (i.e. database-style) queries. The LDAP model enables highly distributed management of entries across directory servers in the network, while still permitting a conceptually unified view of the data.
To achieve fast performance and high availability to systems on a network, it is desirable to cache information close to the client applications that access the server information. Caching is used extensively on the Internet today, e.g. in proxy servers and client browsers, to reduce user-perceived latency and improve overall network performance. Co-pending, commonly-assigned utility application, “METHOD AND APPARATUS FOR OPTIMIZING QUERIES ON NETWORK DIRECTORY CACHES,” Ser. No. 09/448,811, filed on Nov. 24, 1999, (Received Notice of Abandonment dated Feb. 4, 2003) which is incorporated by reference herein, disclosed that cached directory entries can be reused in answering certain declarative queries. The use of semantic information in the client cache—although shown to be advantageous for efficient handling of declarative queries—also imposes a very high cost when individual user queries select just one or a few directory entries, as is often the case in many real LDAP applications. The storage overhead of maintaining the meta data that semantically describe the directory entries in the client cache becomes comparable to the size of the cached data, and the computational overhead of searching the meta data to determine if a user query can be answered from the cache becomes prohibitive.